#!/usr/bin/env python3
# coding: utf-8

import random, timeit


def remove_duplicates(ms):
    assert len(ms) >= 1
    i = 1  # current element
    s = 0  # length of sorted part aka index of next swap element
    while i < len(ms):
        if ms[i] != ms[s]:
            s += 1
            ms[i], ms[s] = ms[s], ms[i]
        i += 1


if __name__ == "__main__":
    for seq in ([1] * 2 + [2] + [4] * 3 + [5] * 2 + [6],
                [1, 2, 2, 3, 3, 4, 4]):
        print(seq)
        remove_duplicates(seq)
        print(seq)
        print('-' * 79)

    for k in range(1, 7):
        seq = [None] * 10 ** k
        acc = 0
        i = 0
        while i < len(seq):
            jump = random.randint(1, 3)
            acc += random.randint(0, 2)
            seq[i:i + jump] = [acc] * jump
            i += jump
        #print(seq)
        t = timeit.Timer('remove_duplicates(seq)', 'from ' + __name__ +
                         ' import remove_duplicates, seq')
        print(k, '\t', t.timeit(1), 'ms')
        #print(seq)
